package org.mmtk.plan.metrix;

import org.mmtk.utility.Log;
import org.mmtk.vm.VM;
import org.vmmagic.pragma.Inline;
import org.vmmagic.pragma.Uninterruptible;
import org.vmmagic.unboxed.ObjectReference;
import org.vmmagic.unboxed.ObjectReferenceArray;

@Uninterruptible
public class TraceHistory implements Ballancer {
	private static final int HISTORY_SIZE = 10;
	private static final double SKEW = 0.3;

	// private TraceHistoryElement[] history;
	private long[] level;
	private ObjectReferenceArray objectRefs;
	private int insertIndex;
	private int firstIndex;
	private int setPointers;

	TraceHistory() {
		// history = new TraceHistoryElement[HISTORY_SIZE];
		// for(int i = 0; i < HISTORY_SIZE; i++) {
		// history[i] = new TraceHistoryElement();
		// }
		level = new long[HISTORY_SIZE];
		objectRefs = ObjectReferenceArray.create(HISTORY_SIZE);
		reset();
		// dump();
	}

	@Inline
	void dump() {
		Log.write("TraceHistory: insertIndex=");
		Log.write(insertIndex);
		Log.write(" firstIndex=");
		Log.writeln(firstIndex);
		for (int i = 0; i < HISTORY_SIZE; i++) {
			// history[i].dump();
			Log.write("i=");
			Log.write(i);
			Log.write(" level=");
			Log.write(level[i]);
			Log.write(" address=");
			Log.writeln(objectRefs.get(i));
		}
	}

	@Inline
	public void reset() {
		this.insertIndex = 0;
		this.firstIndex = 0;
		this.setPointers = 0;
		// dump();
	}

	public void report() {
		Log.write("TraceHistory report, setPointers=");
		Log.writeln(this.setPointers);
		Log.flush();
	}

	@Inline
	private boolean isEmpty() {
		return this.insertIndex == this.firstIndex;
	}

	@Inline
	private boolean isFull() {
		int next = this.insertIndex + 1;
		if (next == HISTORY_SIZE) {
			next = 0;
		}
		return next == this.firstIndex;
	}

	// pop the last assuming not empty
	@Inline
	private void pop() {
		if (VM.VERIFY_ASSERTIONS) {
			VM.assertions._assert(!isEmpty());
		}
		this.insertIndex--;
		if (this.insertIndex == -1) {
			this.insertIndex = HISTORY_SIZE - 1;
		}
	}

	@Inline
	private boolean tryPop() {
		if (!isEmpty()) {
			pop();
			return true;
		}
		return false;
	}

	// remove the first assuming not empty
	@Inline
	private void remove() {
		if (VM.VERIFY_ASSERTIONS) {
			VM.assertions._assert(!isEmpty());
		}
		this.firstIndex++;
		if (this.firstIndex == HISTORY_SIZE) {
			this.firstIndex = 0;
		}
	}

	@Inline
	private boolean tryRemove() {
		if (this.insertIndex != this.firstIndex) {
			remove();
			return true;
		}
		return false;
	}

	// push assuming not full
	@Inline
	private void push(ObjectReference objectRef, long level, int children) {
		if (VM.VERIFY_ASSERTIONS) {
			VM.assertions._assert(!isFull());
		}
		// Log.write("TraceHistory push, insertIndex=");
		// Log.writeln(this.insertIndex);
		// Log.flush();
		// TraceHistoryElement element = history[this.insertIndex];
		// Log.write("TraceHistory push, element=");
		// if(element == null) {
		// Log.writeln("null");
		// } else {
		// element.dump();
		// }
		objectRefs.set(this.insertIndex, objectRef);
		this.level[this.insertIndex] = level;
		this.insertIndex++;
		if (this.insertIndex == HISTORY_SIZE) {
			this.insertIndex = 0;
		}
	}

	@Inline
	private boolean tryPush(ObjectReference objectRef, long level, int children) {
		if (!isFull()) {
			push(objectRef, level, children);
			return true;
		}
		return false;
	}

	// force the push by removing the first element if needed
	@Inline
	private void forcePush(ObjectReference objectRef, long level, int children) {
		if (isFull()) {
			remove();
		}
		push(objectRef, level, children);
	}

	@Inline
	private int popTillLevel(long level) {
		int result = 0;
		while (level < this.level[this.insertIndex]) {
			if (!tryPop()) {
				break;
			}
			result++;
		}
		return result;
	}

	@Inline
	private int removeFirstLevel() {
		long firstLevel = level[this.firstIndex];
		remove();
		int removed = 1;

		while (firstLevel == level[this.firstIndex]) {
			if (!tryRemove()) {
				break;
			}
			removed++;
			if (removed > HISTORY_SIZE * SKEW) {
				break;
			}
		}
		return removed;
	}

	// must not be empty
	@Inline
	private int getIndexOfLast() {
		if (this.insertIndex == 0) {
			return HISTORY_SIZE - 1;
		} else
			return this.insertIndex - 1;
	}

	@Inline
	public void process(ObjectReference objectRef, long level, int children) {
		if (children == 0) {
			return;
		}
		if (isEmpty()) {
			push(objectRef, level, children);
			return;
		}
		// history is not empty
		long lastLevel = this.level[getIndexOfLast()];
		if (level >= lastLevel) {
			// try to insert
			if (!tryPush(objectRef, level, children)) {
				// too many elements, add narrow reference from the first to
				// this new one
				ObjectReference from = objectRefs.get(this.firstIndex);
				ObjectReference narrowRef = VM.objectModel.getKathy(from);
				if (ObjectReference.nullReference() != narrowRef) {
					// already set
				} else {
					VM.objectModel.setKathy(from, objectRef);
					this.setPointers++;
				}
				int removed = removeFirstLevel();
				push(objectRef, level, children);
			}
		} else {
			int removed = popTillLevel(level);
			boolean inserted = tryPush(objectRef, level, children);
		}
	}
}
